package leetcode._06_回溯;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author pppppp
 * @date 2022/3/9 14:48
 * 输入：board =
 * 输出：
 * [["5","3","4","6","7","8","9","1","2"],
 * ["6","7","2","1","9","5","3","4","8"],
 * ["1","9","8","3","4","2","5","6","7"],
 * ["8","5","9","7","6","1","4","2","3"],
 * ["4","2","6","8","5","3","7","9","1"],
 * ["7","1","3","9","2","4","8","5","6"],
 * ["9","6","1","5","3","7","2","8","4"],
 * ["2","8","7","4","1","9","6","3","5"],
 * ["3","4","5","2","8","6","1","7","9"]]
 */
public class _37_解数独 {
    char[][] board = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
    };

    @Test
    public void T_() {
        solveSudoku(board);
        System.out.println();
    }

    Character[] basic = {' ', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    /*2.leetcode 官方题解*/
    /*使用布尔值来表示1-9的数字是否使用过了 使用List 保存需要填入的数字的坐标(i,j)*/
    @Test
    public void T_2() {
        solveSudoku2(board);
        System.out.println();
    }

    boolean[][] row = new boolean[9][9];
    boolean[][] col = new boolean[9][9];
    boolean[][] rank = new boolean[9][9];
    List<int[]> spaces = new ArrayList<>();

    public void solveSudoku2(char[][] board) {
        /*对数据进行处理  存在数字的行列的位置都置为true*/
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    spaces.add(new int[]{i, j});
                } else {
                    int num = board[i][j] - '1';
                    row[i][num] = true;
                    col[j][num] = true;
                    rank[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs2(board, 0);
    }



    private boolean dfs2(char[][] board, int pos) {

        if (pos == spaces.size()) {
            return true;
        }
        int[] p = spaces.get(pos);
        int i = p[0], j = p[1];
        for (int k = 0; k < 9; k++) {
            /*判断数字k是否存在于 行、列、块中*/
            if (!row[i][k] && !col[j][k] && !rank[i / 3 * 3 + j / 3][k]) {
                board[i][j] = String.valueOf(1 + k).charAt(0);
                row[i][k] = true;
                col[j][k] = true;
                rank[i / 3 * 3 + j / 3][k] = true;

                if(dfs2(board, pos + 1)){
                    return true;
                }
                row[i][k] = false;
                col[j][k] = false;
                rank[i / 3 * 3 + j / 3][k] = false;
            }
        }
        return false;
    }





    /*数独 1.网友的解法*/
    public void solveSudoku(char[][] board) {
        List<HashSet<Integer>> h = new ArrayList<>();
        List<HashSet<Integer>> l = new ArrayList<>();
        List<HashSet<Integer>> rank = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            rank.add(new HashSet<>());
        }

        HashSet<Integer> lx = new HashSet<>();
        HashSet<Integer> rx = new HashSet<>();

        for (int i = 0; i < 9; i++) {
            HashSet<Integer> hset = new HashSet<>();
            HashSet<Integer> lset = new HashSet<>();
            for (char c : board[i]) {
                if (c != '.') {
                    hset.add(Character.getNumericValue(c));
                }
            }
            h.add(hset);
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.') {
                    lset.add(Character.getNumericValue(board[j][i]));
                    rank.get(i / 3 * 3 + j / 3).add(Character.getNumericValue(board[i][j]));
                    if (i == j) {
                        lx.add(Character.getNumericValue(board[i][j]));
                    } else if (i + j == 8) {
                        rx.add(Character.getNumericValue(board[i][j]));
                    }

                }
            }
            l.add(lset);

        }
        dfs(0, 0, board, h, l, rank, false);

    }

    /*判断 (i,j) 处的是否存在可以填入的合适的数据*/
    private boolean dfs(int row, int col, char[][] board, List<HashSet<Integer>> h, List<HashSet<Integer>> l, List<HashSet<Integer>> rank, boolean finish) {

        if (col == 9) {
            col = 0;
            row++;
            if (row == 9) {
                return true;
            }
        }

        if (board[row][col] == '.') {
            for (int j = 1; j <= 9; j++) {
                if (!h.get(row).contains(j) && !l.get(col).contains(j) && !rank.get(row / 3 * 3 + col / 3).contains(j)) {

                    board[row][col] = basic[j];
                    h.get(row).add(j);
                    l.get(col).add(j);
                    rank.get(row / 3 * 3 + col / 3).add(j);

                    /*存在符合条件就不用回溯*/
                    if (dfs(row, col + 1, board, h, l, rank, finish)) {
                        return true;
                    } else {
                        /*不存在符合条件的就要进行回溯 若所有的都不合适则 在最后面处返回false*/
                        board[row][col] = '.';
                        h.get(row).remove(j);
                        l.get(col).remove(j);
                        rank.get(row / 3 * 3 + col / 3).remove(j);
                    }
                }
            }
        } else {
            return dfs(row, col + 1, board, h, l, rank, finish);
        }
        /*for循环遍历完后依然找不到合适的数据*/
        return false;
    }


    /*对角线数独*/
    // private void dfs_djx(int row, int col, char[][] board, List<HashSet<Integer>> h, List<HashSet<Integer>> l, HashSet<Integer> lx, HashSet<Integer> rx, List<HashSet<Integer>> rank) {
    //     for (int i = col; i < 9; i++) {
    //         if (board[row][i] == '.') {
    //             for (int j = 1; j <= 9; j++) {
    //                 if (!h.get(row).contains(j)) {
    //                     if (l.get(i).contains(j) || rank.get(row / 3 * 3 + i / 3).contains(j)) {
    //                         continue;
    //                     }
    //                     if (i == row) {
    //                         if (lx.contains(j)) {
    //                             continue;
    //                         }
    //                     } else if (i + row == 8) {
    //                         if (rx.contains(j)) {
    //                             continue;
    //                         }
    //                     }
    //
    //                     board[row][i] = basic[j];
    //                     if (board[1][6] == '3') {
    //                         System.out.println();
    //                     }
    //                     h.get(row).add(j);
    //                     l.get(i).add(j);
    //                     rank.get(row / 3 * 3 + i / 3).add(j);
    //                     if (i == row) {
    //                         lx.add(j);
    //                     } else if (i + row == 8) {
    //                         rx.add(j);
    //                     }
    //                     if (i == 8) {
    //                         dfs_djx(row + 1, 0, board, h, l, lx, rx, rank);
    //                     } else {
    //                         dfs_djx(row, i + 1, board, h, l, lx, rx, rank);
    //                     }
    //
    //                     board[row][i] = '.';
    //                     h.get(row).remove(j);
    //                     l.get(i).remove(j);
    //                     rank.get(row / 3 * 3 + i / 3).remove(j);
    //                     if (i == row) {
    //                         lx.remove(j);
    //                     } else if (i + row == 8) {
    //                         rx.remove(j);
    //                     }
    //                 }
    //
    //             }
    //             /*没有可以填入的元素*/
    //             if (board[row][i] == '.') {
    //                 return;
    //             }
    //
    //
    //         }
    //     }
    // }
}
